/*
	Header file
	-----------
	DL_List.h

	Description:
	------------
	Template declaration for DL_List and DL_Node
	includes all method, attributes and relevent properties

 */


#ifndef _DL_LIST_
#define _DL_LIST_

#include "Monom.h"      // used for cout << DL_List<Monom>
#include <iostream>     // used for cout()
#include <stdlib.h>     // used for exit()

using namespace std;


// Node inside DL_List
template <class T>
class DL_Node
{
public:
	template <class T>
	friend class DL_List;	// allow DL_List to access properties & fields

    // output stream
    template <class T>
	friend ostream& operator<< (ostream &out, const DL_List<T> &L);

	// constructors & destructor
    DL_Node<T>::DL_Node() {};							// constructor
    DL_Node<T>::~DL_Node() {};							// destructor
//	Is it necessary at all ?
//	DL_Node<T>::DL_Node(const DL_Node<T> &T);		// copy constructor
	

private:
	T data;
	DL_Node *prev;
	DL_Node *next;
};

template <class T>
class DL_List
{
	// operator<<() - prints the contents of the list
    template <class T>
	friend ostream& operator<< (ostream &out, const DL_List<T> &L);

public:

	// constructors & destructors
    DL_List(): head(NULL), tail(NULL) {};   	// constructor
    ~DL_List() { this->Clear(); };			    // destructor
//	Is it necessary at all ?
	DL_List(const DL_List &l);		// copy constructor

	// methods
    T* Front() {                        // returns a pointer to the first item in the list
        return ((this->head == NULL) ? NULL : &(this->head->data));
    };
    
    const T* Front() const { 			// returns a const-pointer to the first item in the list
        return ((this->head == NULL) ? NULL : &(this->head->data));
    };
    T* Back() {							// returns a pointer to the last item in the list
        return ((this->tail == NULL) ? NULL : &(this->tail->data));
    };
    const T* Back() const {				// returns a const-pointer to the first item in the list
        return ((this->tail == NULL) ? NULL : &(this->tail->data));
    };
	void PushFront(const T&);			// inserts an item to the start of the list
	void PushBack(const T&);			// inserts an item to the end of the list
	void PopFront();					// removes an item from the start of the list
	void PopBack();						// removes an item from the end of the list
	void Sort();						// sorts the elements in the list. Remember that you don't know the type of the list elements
	void Remove(const T&);				// removes all elements from the list which are equal to the parameter
	void Clear();						// removes all elements from the list
	bool Exists(const T&) const;		// returns true if an item that is equal to the parameter exists in the list
	bool Empty() const { return (Size() == 0); }; // returns true if the list is empty and false otherwise
	int Size() const;					// returns the number of elements in the list
	T* At(const int index) { return operator[](index); };	// returns a pointer to the element in the index position in the list. Assume the index exists. The index of the first element is zero
	const T* At(int index) const { return operator[](index); };		// returns a const-pointer to the element in the index position in the list. An OutOfBounds Exception should be thrown if such index does not exist

	// operators
	T* operator[](const int index);					// index operator - full access assignment
	const T* operator[](const int index) const;		// index operator - read only

private:
	DL_Node<T> *head;
	DL_Node<T> *tail;
};




/*****************************************************
 DL_List - template methods & operators implementation
 *****************************************************/

// cout identifier - output to screen

template <class T>
ostream& operator<< (ostream &out, const DL_List<T> &L)
{
    DL_Node<T> *iter = L.head;
    while (iter != NULL)
    {
        out << iter->data << " ";
        iter = iter->next;
    }

    return out;
}


// cout identifier - output DL_List<Monom> to screen
template <>
inline ostream& operator<< (ostream &out, const DL_List<Monom> &L)
{
    DL_Node<Monom> *iter = L.head;

	int i = 0;

    while (iter != NULL)
    {
 		if ((i > 0) && (iter->data.getC() > 0))
			cout << "+";
		out << iter->data << " ";
        iter = iter->next;
		i++;
    }

    return out;
}

// Copy constructor
template <class T>
DL_List<T>::DL_List(const DL_List &l)
{
}

// Methods


// inserts an item to the start of the list
template <class T>
void DL_List<T>::PushFront(const T& T1)
{
	// head == null
	if (Size() == 0) {
		this->head = this->tail = new DL_Node<T>;
        if (this->head == NULL)
        {
            cout << "Memory allocation failed." << endl;
            exit(1);
        }
		head->next = head->prev = NULL;
		head->data = T1;
	} else
	{
		DL_Node<T>* temp = this->head;			// save original head
		DL_Node<T>* newHead = new DL_Node<T>;   // allocate memory for new head
        if (newHead == NULL)
        {
            cout << "Memory allocation failed." << endl;
            exit(1);
        }
		newHead->next = temp;					// new head --> old head
		newHead->data = T1;						// assign data for newhead
		newHead->prev = NULL;					// NULL <-- new head
		temp->prev = newHead;					// new head <-- old head
		this->head = newHead;					// this->head = newHead
	}
}

// inserts an item to the start of the list
template <class T>
void DL_List<T>::PushBack(const T& T1)
{
	// head == null
	if (Size() == 0) {
		this->head = this->tail = new DL_Node<T>;
        if (this->head == NULL)
        {
            cout << "Memory allocation failed." << endl;
            exit(1);
        }
		head->next = head->prev = NULL;
		head->data = T1;
	} else
	{
		DL_Node<T>* newTail = new DL_Node<T>;
        if (newTail == NULL)
        {
            cout << "Memory allocation failed." << endl;
            exit(1);
        }
		newTail->data = T1;
		newTail->prev = this->tail;
		newTail->next = NULL;
		this->tail->next = newTail;
		this->tail = newTail;
	}
}

// removes an item from the start of the list
template <class T>
void DL_List<T>::PopFront()
{
	// Empty list ?
    if (this->Size() == 0)
        return;
	
	// Save this->head->next
	DL_Node<T> *headNext = this->head->next;

	// Release allocated memory (current head)
	delete this->head;

	// Update newHead->prev = NULL
	this->head = headNext;
	if (this->head != NULL)
		this->head->prev = NULL;

	// Empty linked list ? update tail accordingly
	if (this->head == NULL)
		this->tail = this->head;

}


// removes an item from the end of the list
template <class T>
void DL_List<T>::PopBack()
{
	// Empty list ?
    if (this->Size() == 0)
        return;
	
	// Save this->tail->prev
	DL_Node<T> *tailPrev = this->tail->prev;

	// Release allocated memory (current tail)
   	delete this->tail;

	// Update newTail->next = NULL
	this->tail = tailPrev;
	if (this->tail != NULL)
		this->tail->next = NULL;

	// Empty linked list ? update head accordingly
	if (this->tail == NULL)
		this->head = this->tail;

}

// sorts the linked list
template <class T>
void DL_List<T>::Sort()
{
    int i,j;
    T current;
    int n=Size();
    for (i = 1; i < n; i++) {     /* find space for the i-th number */
        current = *(this->operator [](i));    /* the current number to store */
        for (j = i; j > 0 && *(this->operator [](j-1)) > current; j--) 
        {
    	    *(this->operator [](j)) = *(this->operator [](j-1)); /* make space */
        }
        T* temp=(this->operator [](j));
        *temp = current;    /* store current number in the space made */
    }
}



// removes all elements from the list which are equal to the parameter
template <class T>
void DL_List<T>::Remove(const T& T1)
{
	DL_Node<T> *iter = this->head;
    DL_Node<T> *iterPrev = NULL;

	while (iter != NULL)
	{
		// Found matching node
		if (iter->data == T1)
		{
			if (iter == this->head)				// matching node is head
            {
				PopFront();
                iter = this->head;
            }
			else if (iter == this->tail)		// matching node is tail
            {
				PopBack();
                return;
            }
			else {								// matching node is in-between
				iter->prev->next = iter->next;
				iter->next->prev = iter->prev;
                iterPrev = iter->prev;
				delete iter;
                iter = iterPrev;
			}
		}
        if (iter != NULL)
    		iter = iter->next;
	}
}


// removes all elements from the list
template <class T>
void DL_List<T>::Clear()
{

	DL_Node<T> *iter = this->head;

	// Empty linked-list
	if (iter == NULL)
		return;

	// delete all nodes
	iter = iter->next;
	while (iter != NULL)
	{
		delete iter->prev;
		iter = iter->next;
	}

	// delete last node
	delete tail;

	// update new head & tail
	this->head = this->tail = NULL;
}


// returns true if an item that is equal to the parameter exists in the list
template <class T>
bool DL_List<T>::Exists(const T& T1) const
{
	DL_Node<T> *iter = this->head;

	while (iter != NULL)
	{
		// Found matching node
		if (iter->data == T1)
			return true;
		iter = iter->next;
	}
	return false;
}


// returns the number of elements in the list
template <class T>
int DL_List<T>::Size() const
{
	DL_Node<T> *iter = this->head;		// point to head of the list
	int counter = 0;					// counter = 0
	while (iter != NULL)				// loop over all elements in linked-list
	{
		counter++;
		iter = iter->next;
	}
	return counter;
}

// index operator[] - non-const version
template <class T>
T* DL_List<T>::operator[](const int index)					// index operator - full access assignment
{
	if (index < 0 || index > (Size() - 1)) 
        return NULL;
            
	// Index is in valid range
	DL_Node<T> *iter = this->head;		// point to head of the list

	int counter = 0;					// counter = 0
	while (index != counter)			// loop over all elements in linked-list
	{
		counter++;
		iter = iter->next;
	}

	// Index is found - return data
	return &(iter->data);

}

// index operator[] - read only
template <class T>
const T* DL_List<T>::operator[](const int index) const
{
		if (index < 0 || index > (Size() - 1)) 
            return NULL;
            
	// Index is valid
	DL_Node<T> *iter = this->head;		// point to head of the list
	int counter = 0;					// counter = 0
	while (index != counter)			// loop over all elements in linked-list
	{
		counter++;
		iter = iter->next;
	}

	// Index is found - return data
	return &(iter->data);

}




#endif